package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/**
 *
 * @param num int整型一维数组
 * @return TreeNode类
 */
func sortedArrayToBST(num []int) *TreeNode {
	// write code here
	return preOrder(num, 0, len(num)-1)
}

func preOrder(num []int, left, right int) *TreeNode {
	if left > right {
		return nil
	}
	// 1. 找到中间节点
	mid := left + (right-left+1)/2
	// 2. 递归构建左右
	root := &TreeNode{
		Val:   num[mid],
		Left:  preOrder(num, left, mid-1),
		Right: preOrder(num, mid+1, right)}
	return root
}
